package tianhao.luo.algorithm;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 马踏棋盘/骑士周游算法
 *
 * @author: tianhao.luo@hand-china.com 2021/7/3  下午5:35
 */
public class HorseChessboard {
    /**
     * 棋盘的行数
     */
    private int X;
    /**
     * 棋盘的行数
     */
    private int Y;


    /**
     * 创建一个数组,标记棋盘的各个位置是否被访问过
     */
    private boolean visited[];
    /**
     * 使用一个属性,标记是否棋盘的所有位置都被访问
     * true表示成功
     */
    private boolean finished;

    /**
     * 棋盘
     */
    private int[][] chessboard;

    public HorseChessboard(int x, int y) {
        this.X = x;
        this.Y = y;
        // 创建棋盘
        this.chessboard = new int[X][Y];
        this.visited = new boolean[X * Y];
    }

    /**
     * 完成马踏棋盘/骑士周游算法
     *
     * @param row    马儿当前的位置的行 从0开始
     * @param column 马儿当前的位置的列 从0开始
     * @param step   是第几步,初始位置就是第一步
     */
    public void traversalChessboard(int row, int column, int step) {
        chessboard[row][column] = step;
        // 把棋盘从第一行开始往后延续,组成一维数组
        visited[row * X + column] = true;
        // 获取当前结点可以走的下一个位置集合
        ArrayList<Point> ps = next(new Point(column, row));
        // 对ps进行排序,排序的规则就是对ps的所有Point对象的下一步的位置的数目,进行非递减排序
//        sort(ps);
        // 遍历ps
        while (!ps.isEmpty()) {
            // 取出一个位置(可以走的)
            Point point = ps.remove(0);
            // 判断该点是否已经被访问过
            if (!visited[point.y * X + point.x]) { // 还没有被访问过
                traversalChessboard(point.y, point.x, step + 1);
            }
        }
        // 判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,表示没有完成任务,将整个棋盘置零
        // step < X * Y成立的情况有两种
        // 1.棋盘到目前为止,仍然没有走完
        // 2.棋盘已经走完,但处于回溯中
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    public void show() {
        for (int i = 0; i < chessboard.length; i++) {
            System.out.println(Arrays.toString(chessboard[i]));
        }
    }

    /**
     * 根据当前位置,计算马儿还能走哪些位置,并放入一个集合中,最多有8个位置(马走日字)
     *
     * @param currPoint
     * @return
     */
    public ArrayList<Point> next(Point currPoint) {
        ArrayList<Point> points = new ArrayList<>();
        // 创建一个point
        Point p1 = new Point();
        // currPoint.x - 2表示左移两位还有距离,currPoint.y - 1表示还可以上移一位
        // 走图中的5
        if ((p1.x = currPoint.x - 2) >= 0 && (p1.y = currPoint.y - 1) >= 0) {
            points.add(new Point(p1));
        }
        // 走图中的6
        if ((p1.x = currPoint.x - 1) >= 0 && (p1.y = currPoint.y - 2) >= 0) {
            points.add(new Point(p1));
        }
        // 走图中的7
        // 注意判断条件中p1的索引不能等于X或Y
        if ((p1.x = currPoint.x + 1) < X && (p1.y = currPoint.y - 2) >= 0) {
            points.add(new Point(p1));
        }
        // 走图中的0
        if ((p1.x = currPoint.x + 2) < X && (p1.y = currPoint.y - 1) >= 0) {
            points.add(new Point(p1));
        }
        // 走图中的1
        if ((p1.x = currPoint.x + 2) < X && (p1.y = currPoint.y + 1) < Y) {
            points.add(new Point(p1));
        }
        // 走图中的2
        if ((p1.x = currPoint.x + 1) < X && (p1.y = currPoint.y + 2) < Y) {
            points.add(new Point(p1));
        }
        // 走图中的3
        if ((p1.x = currPoint.x - 1) >= 0 && (p1.y = currPoint.y + 2) < Y) {
            points.add(new Point(p1));
        }
        // 走图中的4
        if ((p1.x = currPoint.x - 2) >= 0 && (p1.y = currPoint.y + 1) < Y) {
            points.add(new Point(p1));
        }

        return points;
    }

    /**
     * 根据当前这一步的所有下一步的选择位置,进行非递减排序(1, 2, 2, 2, 3,3, 4, 5, 6)
     * 减少回溯;因为走的步数越少,回溯也就越少
     */
    public void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                // 获取到o1点的下一步的所有位置的个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                // 返回值小于0,o1和o2不发生交换
                if (count1 < count2){
                    return -1;
                }else if (count1 == count2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}
